package com.practice.niuke.new_direct_practice.class11;

/**
 * int[] d，d[i]：i号怪兽的能力
 * int[] p，p[i]：i号怪兽要求的钱
 * 开始时你的能力是0，你的目标是从0号怪兽开始，通过所有的怪兽。
 * 如果你当前的能力，小于i号怪兽的能力，你必须付出p[i]的钱，贿赂这个怪兽，然后
 * 怪兽就会加入你，他的能力直接累加到你的能力上；如果你当前的能力，大于等于i号
 * 怪兽的能力，你可以选择直接通过，你的能力并不会下降，你也可以选择贿赂这个怪
 * 兽，然后怪兽就会加入你，他的能力直接累加到你的能力上。
 * 返回通过所有的怪兽，需要花的最小钱数。
 */
public class Code04_MoneyProblem {

    // int[] d     d[i]：i号怪兽的武力
    // int[] p     p[i]：i号怪兽要求的钱
    // hp          当前你所具有的能力
    // index       来到了第index个怪兽的面前

    // 目前，你的能力是hp，你来到了index号怪兽的面前，如果要通过后续所有的怪兽，
    // 请返回需要花的最少钱数
    public static long process(int[] d, int[] p, int hp, int index) {
        if (index == d.length) {
            return 0;
        }
        if (hp < d[index]) {
            return p[index] + process(d, p, hp + d[index], index + 1);
        } else { // 可以贿赂，也可以不贿赂
            return Math.min(
                    p[index] + process(d, p, hp + d[index], index + 1),
                    process(d, p, hp, index + 1));
        }
    }

    public static long func1(int[] d, int[] p) {
        return process(d, p, 0, 0);
    }

    public static long func2(int[] d, int[] p) {
        int sum = 0;
        for (int num : d) {
            sum += num;
        }
        long[][] dp = new long[d.length + 1][sum + 1];
        for (int i = 0; i <= sum; i++) {
            dp[0][i] = 0;
        }
        for (int cur = d.length - 1; cur >= 0; cur--) {
            for (int hp = 0; hp <= sum; hp++) {
                // 如果这种情况发生，那么这个hp必然是递归过程中不会出现的状态
                // 既然动态规划是尝试过程的优化，尝试过程碰不到的状态，不必计算
                if (hp + d[cur] > sum) {
                    continue;
                }
                if (hp < d[cur]) {
                    dp[cur][hp] = p[cur] + dp[cur + 1][hp + d[cur]];
                } else {
                    dp[cur][hp] = Math.min(p[cur] + dp[cur + 1][hp + d[cur]], dp[cur + 1][hp]);
                }
            }
        }
        return dp[0][0];
    }

    public static long func3(int[] d, int[] p) {
        int sum = 0;
        for (int num : p) {
            sum += num;
        }
        // dp[i][j]含义：
        // 能经过0～i的怪兽，且花钱为j（花钱的严格等于j）时的武力值最大是多少？
        // 如果dp[i][j]==-1，表示经过0～i的怪兽，花钱为j是无法通过的，或者之前的钱怎么组合也得不到正好为j的钱数
        int[][] dp = new int[d.length][sum + 1];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j <= sum; j++) {
                dp[i][j] = -1;
            }
        }
        // 经过0～i的怪兽，花钱数一定为p[0]，达到武力值d[0]的地步。其他第0行的状态一律是无效的
        dp[0][p[0]] = d[0];
        for (int i = 1; i < d.length; i++) {
            for (int j = 0; j <= sum; j++) {
                // 可能性一，为当前怪兽花钱
                // 存在条件：
                // j - p[i]要不越界，并且在钱数为j - p[i]时，要能通过0～i-1的怪兽，并且钱数组合是有效的。
                if (j >= p[i] && dp[i - 1][j - p[i]] != -1) {
                    dp[i][j] = dp[i - 1][j - p[i]] + d[i];
                }
                // 可能性二，不为当前怪兽花钱
                // 存在条件：
                // 0~i-1怪兽在花钱为j的情况下，能保证通过当前i位置的怪兽
                if (dp[i - 1][j] >= d[i]) {
                    // 两种可能性中，选武力值最大的
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
                }
            }
        }
        int ans = 0;
        // dp表最后一行上，dp[N-1][j]代表：
        // 能经过0～N-1的怪兽，且花钱为j（花钱的严格等于j）时的武力值最大是多少？
        // 那么最后一行上，最左侧的不为-1的列数(j)，就是答案
        for (int j = 0; j <= sum; j++) {
            if (dp[d.length - 1][j] != -1) {
                ans = j;
                break;
            }
        }
        return ans;
    }

    /**
     * 单个怪兽的能力都不是很大，但是贿赂怪兽的钱数很大时可以使用这个方法（TODO：视频讲解的第一种方法）
     *
     * @param ability ability
     * @param money   money
     * @return
     */
    // ability和money,是正数数组
    public static int minMoney1(int[] ability, int[] money) {
        if (ability == null || money == null || ability.length == 0 || money.length == 0) {
            return 0;
        }
        if (ability.length != money.length) {
            return 0;
        }
        int n = ability.length;
        // 能力值最大的范围为能力的累加和(所有怪兽全部都贿赂的时候取最大值)
        int sum = 0;
        for (int cur : ability) {
            sum += cur;
        }
        // dp[i][j]的含义：从0位置一直通关到i位置（i位置也通关），能力值必须严格达到j的情况下，至少要花多少钱(没有方案时为-1)
        int[][] dp = new int[n][sum + 1];
        // 所有位置先初始化为-1, 默认都没有方案
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = -1;
            }
        }
        // （1）dp[0][j]这一行中（第0行）：只有能力严格达到ability[0]才能通关，
        // 所以只有ad[0][ability[0]]才有方案，所花费的钱数为money[0];其他的位置没有方案
        dp[0][ability[0]] = money[0];
        // （2）因为ability和money都是正数数组，dp的第0列dp[i][0]代表通关到i位置且能力严格达到0的情况，所以dp的第0列都没有方法，为初始值-1就行
        // （3）第0行和第0列之外的其他位置：
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= sum; j++) {
                if (j < ability[i]) {
                    dp[i][j] = -1;
                } else {// j>=ability[i]
                    int p1 = -1;
                    int p2 = -2;
                    // 方案一：从0号怪兽可以一直通关到i-1号怪兽，通关i-1号怪兽是能力严格为j（有这个方案），
                    // 那我通关i号怪兽时一分钱也不花能力维持j就行，总共花费的钱依旧为dp[i - 1][j]
                    if (dp[i - 1][j] != -1) {
                        p1 = dp[i - 1][j];
                    }
                    // 方案二：从0号怪兽可以一直通关到i-1号怪兽，通关i-1号怪兽是能力严格为j-ability[i]（有这个方案），
                    // 该方案花费的钱数为，通关了i-1号怪兽花费的钱数 + 通关i号怪兽时花费的i号怪兽需要的钱数money[i]
                    if (dp[i - 1][j - ability[i]] != -1) {
                        p2 = dp[i - 1][j - ability[i]] + money[i];
                    }
                    // 最终决定
                    dp[i][j] = p1 == -1 || p2 == -1 ? (p1 == -1 ? p2 : p1) : Math.min(p1, p2);
                }

            }
        }
        // dp的最后一行中最小的正数为答案
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < dp[n - 1].length; i++) {
            int cur = dp[n - 1][i];
            if (cur > 0) {
                result = Math.min(cur, result);
            }
        }
        return result;
    }

    /**
     * 单个怪兽的能力很大，但是贿赂怪兽的钱数不大时可以使用这个方法（TODO：视频讲解的第二种方法）
     *
     * @param ability ability
     * @param money   money
     * @return int
     */
    public static int minMoney2(int[] ability, int[] money) {
        if (ability == null || money == null || ability.length == 0 || money.length == 0) {
            return 0;
        }
        if (ability.length != money.length) {
            return 0;
        }
        int n = ability.length;
        // 钱数的累加和
        int sum = 0;
        for (int i = 0; i < money.length; i++) {
            sum += money[i];
        }
        // dp[i][j]的含义：从0号怪兽通关到i号怪兽（i号怪兽也通关），总共花费的钱数必须严格为j的情况下，所能达到的最大能力值（没有方案为-1）。
        long[][] dp = new long[n][sum + 1];
        // 所有位置先初始化为-1, 默认都没有方案
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = -1;
            }
        }
        // （1）第0行，通关第0号怪兽，只能是严格为0号怪兽要求的钱数，所能达到的最大能力为0号怪兽的能力，没有其他方案的方案，因此第0行其他位置为-1
        dp[0][money[0]] = ability[0];
        // (2) 第0列，表示只花费0元，由于money为正数数组，因此第0列没有方案，都为-1
        // （3）第0行和第0列之外的其他位置：
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= sum; j++) {
                long p1 = -1;
                long p2 = -1;
                // 方案一：从0号怪兽通关到i-1号怪兽（第i-1号怪兽也通关）总共所花费的钱数为j的情况下有方案，
                // 且所达到的最大能力dp[i - 1][j]大于第i号怪兽的能力，所有我们可以选择通关i号怪兽时候一分钱不花，
                // 刚好所花费的总的钱数也是j,但是所能到达的最大能力也为dp[i - 1][j]
                if (dp[i - 1][j] != -1 && dp[i - 1][j] >= ability[i]) {
                    p1 = dp[i - 1][j];
                }
                // 方案二：从0号怪兽通关到i-1号怪兽（第i-1号怪兽也通关）总共所花费的钱数为j - money[i]的情况下有方案，
                // 而通关i号怪兽时候所花费的钱为money[i]，所以通关i号怪兽时所花费的钱的总数刚好严格为j,
                // 此时通关i号怪兽时所能达到的最大能力为，
                // 通关i-1号怪兽且总共花费j-money[i]的钱数时达到的最大能力dp[i - 1][j - money[i]] + 通关i号怪兽获得的能力ability[i]
                if (j - money[i] >= 0 && dp[i - 1][j - money[i]] != -1) {
                    p2 = dp[i - 1][j - money[i]] + ability[i];
                }
                // 最终决定
                dp[i][j] = p1 == -1 || p2 == -1 ? (p1 == -1 ? p2 : p1) : Math.max(p1, p2);
            }
        }
        int result = -1;
        for (int i = 0; i < dp[n - 1].length; i++) {
            if (dp[n - 1][i] > 0) {
                result = i;
                break;
            }
        }
        return result;
    }

    public static int[][] generateTwoRandomArray(int len, int value) {
        int size = (int) (Math.random() * len) + 1;
        int[][] arrs = new int[2][size];
        for (int i = 0; i < size; i++) {
            arrs[0][i] = (int) (Math.random() * value) + 1;
            arrs[1][i] = (int) (Math.random() * value) + 1;
        }
        return arrs;
    }

    public static void main(String[] args) {
        int len = 10;
        int value = 20;
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            int[][] arrs = generateTwoRandomArray(len, value);
            int[] d = arrs[0];
            int[] p = arrs[1];
            long ans1 = func1(d, p);
            long ans2 = func2(d, p);
            long ans3 = func3(d, p);
            if (ans1 != ans2 || ans2 != ans3) {
                System.out.println("oops!");
            }
        }

    }

}
